package com.lee.algorithm.kmp;

/***
 * @description kmp 算法
 * @author 青石路
 * @date 2022/1/16 19:55
 */
public class Kmp {

    public static int getIndexOf(String source, String sub) {
        // 边界值考虑
        if(source == null || sub == null || sub.length() < 1 || source.length() < sub.length()) {
            return -1;
        }
        char[] sourceArr = source.toCharArray();
        char[] subArr = sub.toCharArray();
        int i1 = 0;
        int i2 = 0;
        int[] next = getNextArr(subArr);
        while (i1 < sourceArr.length && i2 < subArr.length) {
            if (sourceArr[i1] == subArr[i2]) {
                i1 ++;
                i2 ++;
            } else if (next[i2] == -1) {    // 或 i2 == 0
                // sub 串中，对比的位置已经无法往前跳了
                // source 换起点，与 sub 0 位置开始匹配
                i1 ++;
            } else {
                i2 = next[i2];
            }
        }
        // i1 越界 或者 i2 越界了
        return i2 == subArr.length ? i1 - i2 : -1;
    }

    /**
     * 求 next 数组
     *      i 位置之前的所有字符（0 ~ i-1）
     *      前缀字符（0开始，往后） 与 后缀字符（i-1开，往前），
     *      前缀字符与后缀字符同长度对比
     * @param subArr
     * @return
     */
    public static int[] getNextArr(char[] subArr) {
        if (subArr.length == 1) {
            return new int[] { -1 };
        }
        int[] next = new int[subArr.length];
        next[0] = -1;
        next[1] = 0;
        int i = 2;          // next 下标
        int cn = 0;         // 拿哪个位置的字符和 i-1 位置上的字符对比；
        while (i < next.length) {
            if (subArr[i - 1] == subArr[cn]) {
                cn ++;
                next[i] = cn;
                i ++;
            } else if (cn > 0) {
                // 当前跳到cn的位置的字符和 i-1 位置的字符匹配不上
                cn = next[cn];
            } else {
                next[i++] = 0;
            }
        }
        return next;
    }
}
